//双向链表
#ifndef __DOUBLYLINKEDLIST__HPP
#define __DOUBLYLINKEDLIST__HPP

#include"VirtualLinkedList.hpp"

namespace NgSiuKei {

template<class TheClass>
struct doubly_linked_list_node {
    TheClass val;
    doubly_linked_list_node<TheClass> *prev;
    doubly_linked_list_node<TheClass> *next;
};
#define dll_node doubly_linked_list_node

template<class TheClass>
class DoublyLinkedList: public VirtualLinkedList<TheClass> {
    public:
    DoublyLinkedList(void);
    ~DoublyLinkedList(void);

    public:
    //清空
    void clear(void);
    //获取特定下标的元素值
    TheClass getVal(const U_L_L &index) const;
    //查找数据，返回下标，表没有则抛出异常：EXCEPTION_CAN_NOT_FIND
    U_L_L findVal(const TheClass &val) const;
    //插入数据
    void insertVal(const TheClass &val, const U_L_L &index);
    //删除特定下标的元素，返回元素值
    TheClass deleteWithIndex(const U_L_L &index);
    //打印表
    void print(void);

    private:
    //中间节点，充分利用双向链表特性
    dll_node<TheClass> *intermediateNode;
};

template<class TheClass>
DoublyLinkedList<TheClass>::DoublyLinkedList(void): VirtualLinkedList<TheClass>() {
    this->intermediateNode = nullptr;
}

template<class TheClass>
DoublyLinkedList<TheClass>::~DoublyLinkedList(void) {
    this->clear();
}

template<class TheClass>
void DoublyLinkedList<TheClass>::clear(void) {
    if(nullptr != this->intermediateNode) {
        dll_node<TheClass> *leftNode = this->intermediateNode;
        dll_node<TheClass> *rightNode = this->intermediateNode->next;
        dll_node<TheClass> *currentNode = nullptr;
        //左右遍历删除
        while(nullptr != leftNode || nullptr != rightNode) {
            //左
            if(nullptr != leftNode) {
                currentNode = leftNode;
                leftNode = leftNode->prev;
                delete currentNode;
                currentNode = nullptr;
            }
            //右
            if(nullptr != rightNode) {
                currentNode = rightNode;
                rightNode = rightNode->next;
                delete currentNode;
                currentNode = nullptr;
            }
        }
    }
    this->intermediateNode = nullptr;
    this->size = 0;
}

template<class TheClass>
TheClass DoublyLinkedList<TheClass>::getVal(const U_L_L &index) const {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }
    if(index >= this->size) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }

    const U_L_L intermediateIndex = (this->size-1)/2;//中间下标，若大小是偶数则取小
    if(index == intermediateIndex) {
        return this->intermediateNode->val;
    }

    dll_node<TheClass> *currentNode = this->intermediateNode;
    if(index < intermediateIndex) {//目标在左半边
        const U_L_L step = intermediateIndex-index;
        for(U_L_L i=0; i<step; ++i) {
            currentNode = currentNode->prev;
        }
    }
    else if(index > intermediateIndex) {//目标在右半边
        const U_L_L step = index-intermediateIndex;
        for(U_L_L i=0; i<step; ++i) {
            currentNode = currentNode->next;
        }
    }
    return currentNode->val;
}

template<class TheClass>
U_L_L DoublyLinkedList<TheClass>::findVal(const TheClass &val) const {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }
    dll_node<TheClass> *leftNode = this->intermediateNode;
    dll_node<TheClass> *rightNode = this->intermediateNode->next;
    U_L_L leftIndex = (this->size-1)/2;
    U_L_L rightIndex = leftIndex+1;
    //左右遍历查找
    while(nullptr != leftNode || nullptr != rightNode) {
        //左
        if(nullptr != leftNode) {
            if(val == leftNode->val) {
                return leftIndex;
            }
            leftNode = leftNode->prev;
            leftIndex--;
        }
        //右
        if(nullptr != rightNode) {
            if(val == rightNode->val) {
                return rightIndex;
            }
            rightNode = rightNode->next;
            rightIndex++;
        }
    }
    throw EXCEPTION_CAN_NOT_FIND;
}

template<class TheClass>
void DoublyLinkedList<TheClass>::insertVal(const TheClass &val, const U_L_L &index) {
    if(index > this->size) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }
    
    dll_node<TheClass> *newNode = new dll_node<TheClass>;
    newNode->val = val;

    const U_L_L intermediateIndex = (0 == this->size)?(0):((this->size-1)/2);
    dll_node<TheClass> *currentNode = this->intermediateNode;
    if(0 == index) {//头
        if(0 == this->size) {
            newNode->next = nullptr;
            newNode->prev = nullptr;
            this->intermediateNode = newNode;
        }
        else {
            while(nullptr != currentNode->prev) {
                currentNode = currentNode->prev;
            }
            currentNode->prev = newNode;
            newNode->next = currentNode;
            newNode->prev = nullptr;
        }
    }
    else if(this->size == index) {//尾
        while(nullptr != currentNode->next) {
            currentNode = currentNode->next;
        }
        currentNode->next = newNode;
        newNode->prev = currentNode;
        newNode->next = nullptr;
    }
    else {
        //找到需要被插入位置的节点，也就是说新节点会插入到这个节点的左边
        if(index <= intermediateIndex) {//左
            const U_L_L step = intermediateIndex-index;
            for(U_L_L i=0; i<step; ++i) {
                currentNode = currentNode->prev;
            }
        }
        else {//右
            const U_L_L step = index-intermediateIndex;
            for(U_L_L i=0; i<step; ++i) {
                currentNode = currentNode->next;
            }
        }
        //插入节点
        newNode->next = currentNode;
        newNode->prev = currentNode->prev;
        currentNode->prev->next = newNode;
        currentNode->prev = newNode;
        /*如果上面的这段代码看不懂可以看下面这段，会直观点
        dll_node<TheClass> *prevNode = currentNode->prev;
        prevNode->next = newNode;
        currentNode->prev = newNode;
        newNode->prev = prevNode;
        newNode->next = currentNode;
        */
    }
    //定位中间节点
    if(this->size > 0) {
        if(index <= intermediateIndex && 0 != this->size%2) {
            this->intermediateNode = this->intermediateNode->prev;
        }
        else if(index > intermediateIndex && 0 == this->size%2) {
            this->intermediateNode = this->intermediateNode->next;
        }
    }
    this->size++;
}

template<class TheClass>
TheClass DoublyLinkedList<TheClass>::deleteWithIndex(const U_L_L &index) {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }
    if(index >= this->size) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }

    const U_L_L intermediateIndex = (this->size-1)/2;
    dll_node<TheClass> *deleteNode = this->intermediateNode;
    if(0 == index) {//头
        while(nullptr != deleteNode->prev) {
            deleteNode = deleteNode->prev;
        }
        deleteNode->next->prev = nullptr;
    }
    else if(this->size-1 == index) {//尾
        while(nullptr != deleteNode->next) {
            deleteNode = deleteNode->next;
        }
        deleteNode->prev->next = nullptr;
    }
    else {
        if(index <= intermediateIndex) {
            const U_L_L step = intermediateIndex-index;
            for(U_L_L i=0; i<step; ++i) {
                deleteNode = deleteNode->prev;
            }
        }
        else {
            const U_L_L step = index-intermediateIndex;
            for(U_L_L i=0; i<step; ++i) {
                deleteNode = deleteNode->next;
            }
        }
        deleteNode->prev->next = deleteNode->next;
        deleteNode->next->prev = deleteNode->prev;
    }
    //定位中间节点
    if(this->size > 0) {
        if(index <= intermediateIndex && 0 == this->size%2) {
            this->intermediateNode = this->intermediateNode->next;
        }
        else if(index >= intermediateIndex && 0 != this->size%2) {
            this->intermediateNode = this->intermediateNode->prev;
        }
    }
    this->size--;

    TheClass resultVal;
    if(nullptr != deleteNode) {
        resultVal = deleteNode->val;
        delete deleteNode;
        deleteNode = nullptr;
    }
    return resultVal;
}

template<class TheClass>
void DoublyLinkedList<TheClass>::print(void) {
    //顺序打印
    cout << "打印双向链表（顺序）：[";
    dll_node<TheClass> *currentNode = this->intermediateNode;
    while(nullptr != currentNode->prev) {
        currentNode = currentNode->prev;
    }
    while(nullptr != currentNode) {
        cout << currentNode->val << ' ';
        currentNode = currentNode->next;
    }
    cout << ']' << endl;
    
    // //逆序打印
    // cout << "打印双向链表（逆向）：[";
    // currentNode = this->intermediateNode;
    // while(nullptr != currentNode->next) {
    //     currentNode = currentNode->next;
    // }
    // while(nullptr != currentNode) {
    //     cout << currentNode->val << ' ';
    //     currentNode = currentNode->prev;
    // }
    // cout << ']' << endl;
}

}

#endif